CON/SLK due date assignment and scheduling on a single machine with two agents

We consider scheduling problems involving two agents (agents A and B), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the A‐jobs are decision variables, which are determined by using the common (CON) or slack (SLK) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent A is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent B, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent A, while keeping the objective value of agent B no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo‐polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial‐time approximation scheme. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 416–429, 2016     

Scheduling jobs with piecewise linear decreasing processing times

We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP‐hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP‐hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 531–554, 2003     

A bidirectional heuristic for maximizing the net present value of large‐scale projects subject to limited resources

We consider the scheduling of large‐scale projects to maximize the project net present value given temporal and resource constraints. The net present value objective emphasizes the financial aspects of project management. Temporal constraints between the start times of activities make it possible to handle practical problem assumptions. Scarce resources are an expression of rising cost. Since optimization techniques are not expedient to solve such problems and most heuristic methods known from literature cannot deal with general temporal constraints, we propose a new bidirectional priority‐rule based method. Scheduling activities with positive cash flows as early and activities with negative cash flows as late as possible results in a method which is completed by unscheduling techniques to cope with scarce resources. In a computational experiment, we compare the well‐known serial generation scheme where all activities are scheduled as early as possible with the proposed bidirectional approach. On the basis of a comprehensive data set known from literature containing instances with up to 1002 activities, the efficiency of the new approach is demonstrated. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

The effectiveness of the longest delivery time rule for the flow shop delivery time problem

In the flow shop delivery time problem, a set of jobs has to be processed on m machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize maximum delivery completion time over all the jobs, where the delivery completion time of a job is the sum of its completion time, and the delivery time associated with that job. In this paper, we prove the asymptotic optimality of the Longest Delivery Time algorithm for the static version of this problem, and the Longest Delivery Time among Available Jobs (LDTA) algorithm for the dynamic version of this problem. In addition, we present the result of computational testing of the effectiveness of these algorithms. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

星地距离变化对星地双向时间比对的影响及改正

星地时间同步是卫星导航系统的关键技术,星地双向时间比对能有效提高星地时间同步的精度。在分析了星地距离变化对星地双向时间比对可引起百纳秒量级误差后,提出了前后历元观测数据差分改正方法,通过数学仿真验证该方法能达到纳秒量级精度。     

基于“北斗”卫星的四级车辆指挥管理系统研究

结合"北斗"卫星定位系统的原理和特点,提出了一种基于我国自主研制双星定位系统的四级车辆指挥管理系统的设计,并分析了其组成、主要功能和特点,该系统能有效地对多辆车实行实时管理与监控,有效地提高车辆的指挥管理效率。     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

基于半监督FCM聚类算法的卫星云图分类

针对卫星云图的特点在分类特征集中采用了一种新的特征--差异化特征,该特征反映了云图的内部结构特点,并且具有良好的鲁棒性,能有效地避免云团位置变化对特征的影响.将半监督思想引入到模糊C均值聚类方法(FCM),克服了单纯的FCM方法未考虑领域知识导致的聚类结果的盲目性.半监督FCM方法在聚类过程中加入少量的由领域专家标记的样本,引入专家的领域知识,通过与这些带有类标记的样本进行相似性比较,引导FCM方法的聚类过程.试验结果表明,基于具有差异化特征的云图特征集,半监督FCM方法能有效地提高云图分类的准确率.     

Preemptive parallel‐machine scheduling with a common server to minimize makespan

We consider parallel‐machine scheduling with a common server and job preemption to minimize the makespan. While the non‐preemptive version of the problem is strongly NP‐hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP‐hard even if there is a fixed number of machines. We give a pseudo‐polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP‐hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 388–398, 2017     

北斗多业务卫星系统与应用——论北斗Bs导航

无线电频率是不可再生的资源,频率共用已成为国际电信联盟的共识,多业务融合发展已成为世界卫星无线电系统发展趋势。S频段中2483.5 MHz~2500 MHz被国际电信联盟划分为卫星多业务共用频率,包括卫星无线电定位报告业务、卫星无线电导航业务、卫星移动通信业务三大业务,可以同时提供卫星导航、航路跟踪、遇险救援、信息中继四大功能。介绍了S频段天基系统发展过程、导航通信频率特性、S频段多功能集成前景,我国北斗未来使用S频段导航的应用成果及社会经济效益预测。